class Solution7 {
    public List<List<String>> findLadders(String beginWord, String endWord, List<String> wordList) {
        //返回结果
        List<List<String>> result = new ArrayList<List<String>>();
        //转化为哈希集合，这样查询时不花费时间
        Set<String> dict = new HashSet<String>(wordList);
        //特殊情况返回空值
        if(!dict.contains(endWord)) return result;
        //
        dict.remove(beginWord);
        int wn = beginWord.length();
        boolean found = false;
        //遍历时的层数
        int step = 1;
        //记录每个单词在遍历时的层数
        Map<String, Integer> wordstep = new HashMap<String, Integer>();
        //记录每个单词是从哪个单词变化来的
        Map<String, List<String>> from = new HashMap<>();

        //遍历队列
        Queue<String> queue = new ArrayDeque<String>();
        wordstep.put(beginWord, 0);
        queue.add(beginWord);
        while(!queue.isEmpty()) {
            int nn = queue.size();
            for(int x = 0; x < nn; x++) {
                String word = queue.poll();
                char[] wordchar = word.toCharArray();
                for(int i = 0; i < wn; i++) {
                    char curr = wordchar[i];
                    for(char j = 'a'; j <= 'z'; j++) {
                        wordchar[i] = j;
                        String currs = String.valueOf(wordchar);
                        if(wordstep.containsKey(currs) && wordstep.get(currs) == step) {
                            from.get(currs).add(word);
                            continue;
                        }
                        if(!dict.contains(currs)) {continue;}
                        from.putIfAbsent(currs, new ArrayList<String>());
                        from.get(currs).add(word);
                        wordstep.put(currs, step);
                        dict.remove(currs);
                        queue.offer(currs);
                        if(currs.equals(endWord)) {
                            found = true;
                        }
                    }
                    wordchar[i] = curr;
                }
            }
            step++;
        }

        //回溯
        if(found) {
            Deque<String> tmp = new ArrayDeque<String>();
            tmp.add(endWord);
            backtrack(result, from, beginWord, endWord, tmp);
        }
        return result;
    }
    public void backtrack(List<List<String>> result, Map<String, List<String>> from, String beginWord, String curr, Deque<String> tmp) {
        if(curr.equals(beginWord)) {
            result.add(new ArrayList<String>(tmp));
            return;
        }
        for(String w : from.get(curr)) {
            tmp.addFirst(w);
            backtrack(result, from, beginWord, w, tmp);
            tmp.removeFirst();
        }
    }
}